/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package com.factory.server.algorithms;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author http://www.algoritmy.net
 */
public class Levenshtein {

    /**
     * Vrati seznam vsech vyskytu daneho vzoru (posledni index v textu, tzn. bez
     * presahu) v danem textu v Levenshteinove vzdalenosti maximalne maxDistance
     * http://www.algoritmy.net
     *
     * @param text text
     * @param pattern vzor
     * @param maxDistance maximalni vzdalenost (vcetne)
     * @return seznam vsech vyskytu
     */
    public static List<Integer> levenshteinDistance(String text, String pattern, int maxDistance) {
        List<Integer> l = new ArrayList<Integer>();
        int[] first = new int[pattern.length()];
        int[] second = new int[pattern.length()];

        for (int i = 0; i < first.length; i++) { //inicializace prvniho sloupce
            first[i] = i + 1;
        }

        for (int i = 0; i < text.length(); i++) { //vyplnovani tabulky
            for (int j = 0; j < second.length; j++) {
                if (pattern.charAt(j) == text.charAt(i)) { //pismena souhlasi
                    if (j != 0) {
                        second[j] = first[j - 1];
                    } else {
                        second[j] = 0;
                    }
                } else {
                    //vertikalni predchozi
                    int prevVert = 0;
                    if (j != 0) {
                        prevVert = second[j - 1];
                    }

                    //horizontalni predchozi
                    int prevHor = j;
                    if (i != 0) {
                        prevHor = first[j];
                    }

                    //diagonalni predchozi
                    int prevDiag = 0;
                    if (i != 0 || j != 0) {
                        if (i != 0 && j != 0) {
                            prevDiag = first[j - 1];
                        } else if (i != 0) {
                            prevDiag = 0;
                        } else if (j != 0) { // j != 0
                            prevDiag = first[j - 1];
                        } else {
                            assert true; //tohle nemuze nastat
                        }
                    } else {
                        prevDiag = 0;
                    }

                    second[j] = 1 + Math.min(prevVert, Math.min(prevHor, prevDiag));

                }
            }
            if (second[pattern.length() - 1] <= maxDistance) {
                l.add(i);
            }

            //swap columns
            int[] tmp = first;
            first = second;
            second = tmp;
        }

        return l;
    }
}
